package com.sukaiyi.leetcode._21merge_two_sorted_lists;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * @author sukaiyi
 * @date 2020/05/21
 * @see <a href="https://leetcode-cn.com/problems/merge-two-sorted-lists">题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4, null)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
        ListNode merged = mergeTwoLists(l1, l2);
        Assertions.assertNotNull(merged);
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode root = null;
        ListNode p = null;
        ListNode l1p = l1;
        ListNode l2p = l2;
        while (l1p != null && l2p != null) {
            if (l1p.val < l2p.val) {
                if (root == null) {
                    root = l1p;
                    p = l1p;
                } else {
                    p.next = l1p;
                    p = l1p;
                }
                l1p = l1p.next;
            } else {
                if (root == null) {
                    root = l2p;
                    p = l2p;
                } else {
                    p.next = l2p;
                    p = l2p;
                }
                l2p = l2p.next;
            }
        }
        for (; l1p != null; l1p = l1p.next) {
            p.next = l1p;
            p = p.next;
        }
        for (; l2p != null; l2p = l2p.next) {
            p.next = l2p;
            p = p.next;
        }
        return root;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x, ListNode next) {
            val = x;
            this.next = next;
        }
    }

}
